/*
 * Implementação de um programa que realiza etiquetagem em um segmento
 * de texto dado com base em informações prévias em forma de tabelas de
 * referência usando o algoritmo genético.
 * Autor: Leonardo Hirokazu de Souza Hamada, 17 de junho de 2014.
*/

#include "Rand.h"

#include<iostream>
#include<sstream>
#include<fstream>
#include<algorithm>	// std::sort
#include<cmath> 	// std::log10
#include<utility>	// std::pair
#include <list>         // std::list
#include<vector>	// std::vector
#include<string>	// std::string
#include<map>           // std::map
#include<locale>	// std::isupper

#include<limits>	// std::numeric_limits<double>::lowest();

#define DEPURAR 0
#define TIPO_GENE uint8_t
#define NUMERO_THREADS 2
#define ENTRADAS_CACHE 10000

#if DEPURAR
#define MOSTRAR(X) std::cout<<(X)<<"\n";
#else
#define MOSTRAR(X)
#endif

// Objeto que gera os números aleatórios usado neste programa
static Rand *GNA;

// Quadro de conversão de indices (genes) para nome das etiquetas
static std::vector<std::string> *QUADRO_DE_ABREV_DAS_ETIQUETAS;

// Quadro que contém as frequencias das etiquetas no corpus de referência
static std::vector<std::size_t> *QUADRO_DE_FREQ_DAS_ETIQUETAS;

// Mapa de conversão reversa que mapeia os nomes das etiquetas para os indices
static std::map<std::string,TIPO_GENE> *TABELA_NUMERICA_ETIQUETAS;

// Etiquetas totais nas palavras do corpus
static std::size_t TotalEtiquetaCorpus;

// Contém os dados de treino e as operações associadas
class TabelasTreinadas
{
public:
    std::size_t l_CE;	    // largura do contexto esquerdo
    std::size_t l_CD;	    // largura do contexto direito
    std::size_t posCentro; // Posição da etiqueta central
    std::size_t l_TOTAL;   // largura conjunta do contexto
    std::size_t NL_CONTEX; // número de contextos lidos
private:
    // Contém os contextos carregados do arquivo pré-processado.
    std::vector<TIPO_GENE *> tabela_contextual;
    // Armazena a quantidade de ocorrência do contexto  indicado  pelo indice que corresponde com o índice da tabela_contextual.
    std::vector<std::size_t> ocorrencias;
    // Lista de palavras conhecidas no corpus.
    std::map<std::string, std::vector<std::pair<TIPO_GENE, std::size_t> > > palavras_conhecidas;
    // Armazena momentaneamente as posições dos contextos lozalizados durante a varredura da tabela_contextual.
    std::vector<std::size_t> posicoes_contextos;
    // Suporte ao idioma
    std::locale *localizacao = NULL;
public:
    // É uma lista incrementalmente calculada que serve para acelerar o cálculo de fitness dado o contexto.
    std::vector<std::tuple<std::vector<TIPO_GENE>,TIPO_GENE,std::vector<TIPO_GENE>,double> > cache_aceleracao;
public:
    TabelasTreinadas()
    {
        CarregarTabelaPalavras();
        CarregarTabelaDeContexto();
		// Reservar entradas no cache.
		cache_aceleracao.reserve(ENTRADAS_CACHE);
    	localizacao = new std::locale("pt_BR.utf8");
    }
    ~TabelasTreinadas()
    {
        auto iter = tabela_contextual.begin();
        for (; iter != tabela_contextual.end(); iter++)
            delete [] *iter;
    	delete localizacao;
    }
    // Tenta localizar no cache o valor do logaritmo decimal da probabilidade da ocorrência contextual dada.
    double localizarNoCacheAcelerado(
        std::vector<TIPO_GENE> &ContexEsq,
        TIPO_GENE etiq_central,
        std::vector<TIPO_GENE> &ContexDir)
    {
        // Procura no cache pela entrada desejada.
		bool encontrado = false;
		std::size_t i, E = cache_aceleracao.size();
		double resultado = 1;
        //for (auto & elemento : cache_aceleracao) {
	#pragma omp parallel for schedule(dynamic,1) default(shared) private(i) num_threads(NUMERO_THREADS)
        for (i = 0; i < E; ++i) {
			#pragma omp flush (encontrado)
			if (!encontrado) {
				auto & elemento = cache_aceleracao[i];
				if ((std::get<0>(elemento) == ContexEsq) &&
						(std::get<1>(elemento) == etiq_central) &&
						(std::get<2>(elemento) == ContexDir)) {
					#if DEPURAR
					std::cout << "Entrada localizada no cache." << std::endl;
					#endif
					//return std::get<3>(elemento);
					resultado = std::get<3>(elemento);
					encontrado = true;
					#pragma omp flush (encontrado)
				}
			}
        }
		return resultado;
    }
    // Tenta manter constante o número de entradas de cache a um tamanho fixo.
//    void limitarTamanhoCacheAcelerado(void)
//    {
//        if (10000 < cache_aceleracao.size())
//            cache_aceleracao.pop_back();
//        #if DEPURAR
//        std::cout << "Limitando o tamanho do cache." << std::endl;
//        #endif
//    }
    // Recupera um gene ao acaso a partir da tabela de palavras conhecidas.
    TIPO_GENE DerivarUmGene(std::string &Palavra)
    {
        auto entrada = palavras_conhecidas.find(Palavra);
	// Estratégia, caso não encontre uma palavra iniciando com maiúscula, tentar a palavra iniciando em minúscula.
       // if ((palavras_conhecidas.end() == entrada) && std::isupper(Palavra.at(0), *localizacao)) {
	//	std::string m = Palavra;
	//	m.at(0) = std::tolower(Palavra.at(0));
        //	entrada = palavras_conhecidas.find(m);
	//}
        if (palavras_conhecidas.end() != entrada) {
            std::vector<std::pair<TIPO_GENE, std::size_t> > &lpc = entrada->second;
            std::size_t soma_freq = 0;
            for (auto &par_etq_freq : lpc) {
                soma_freq += par_etq_freq.second;
            }
            std::size_t num_sorteio = GNA->RandInt(soma_freq);
            for (auto &par_etq_freq : lpc) {
                if (num_sorteio < par_etq_freq.second)
                    return par_etq_freq.first;
                num_sorteio -= par_etq_freq.second;
            }
        } else
            return 0;
    }
    // Recupera um gene apenas pelo contextos laterais.
    TIPO_GENE DerivarUmGenePeloContexto(
        std::vector<TIPO_GENE> &ContexEsq,
        std::vector<TIPO_GENE> &ContexDir)
    {
        std::size_t j;
        std::size_t soma_das_ocorrencias = 0;
        posicoes_contextos.clear();
        #pragma omp parallel default(shared) private(j) num_threads(NUMERO_THREADS)
	{
		#pragma omp for schedule(dynamic,1) nowait
		for (j = 0; j < NL_CONTEX; ++j) {
		    bool localizado = true;
		    std::size_t i;
		    for (i = 1; i <= ContexEsq.size(); ++i) {
			if (tabela_contextual[j][posCentro - i] != ContexEsq[ContexEsq.size() - i]) {
			    localizado = false;
			    break;
			}
		    }
		    if (!localizado) continue;
		    for (i = 1; i <= ContexDir.size(); ++i) {
			if (tabela_contextual[j][posCentro + i] != ContexDir[i - 1]) {
			    localizado = false;
			    break;
			}
		    }
		    if (localizado) {
			#pragma omp critical
			{
			    posicoes_contextos.push_back(j);
			    soma_das_ocorrencias += ocorrencias[j];
			}
		    }
		}
	}
        if (!posicoes_contextos.empty()) {
            //// (Feito)A fazer: Considerar pesos de frequencia neste sorteio.
            std::size_t escolha = 0;// = posicoes_contextos[GNA->RandInt(posicoes_contextos.size())];
            //std::size_t soma_das_ocorrencias = 0;
            //for (auto &pos_tabela_contextual : posicoes_contextos) {
            //    soma_das_ocorrencias += ocorrencias[pos_tabela_contextual];
            //}
            std::size_t num_sorteio = GNA->RandInt(soma_das_ocorrencias);
#if DEPURAR
	    std::cout << "Num. occ. " << soma_das_ocorrencias << std::endl;
#endif
            for (auto &pos_tabela_contextual : posicoes_contextos) {
                if (num_sorteio < ocorrencias[pos_tabela_contextual]) {
                    escolha = pos_tabela_contextual;
                    break;
                }
                num_sorteio -= ocorrencias[pos_tabela_contextual];
                //soma_das_ocorrencias += ocorrencias[pos_tabela_contextual];
            }
            return tabela_contextual[escolha][posCentro];
        } else {
            return 0;
        }
    }
    // Localiza a quantidade de ocorrência dado o contexto da esquerda, a etiqueta central e o contexto da direita.
    // Caso a etiqueta central seja nula ("NULL"==0), esta etiqueta será ignorada e retorna-se as ocorrências contextuais
    // apenas dos contextos laterais.
    std::size_t recuperarOcorrenciasContextuais(
        std::vector<TIPO_GENE> &ContexEsq,
        TIPO_GENE etiq_central,
        std::vector<TIPO_GENE> &ContexDir)
    {
        if ((ContexEsq.size() == 0) && (ContexDir.size() == 0)) {
            if (etiq_central == 0) {
                return TotalEtiquetaCorpus;
            } else {
                return (*QUADRO_DE_FREQ_DAS_ETIQUETAS)[etiq_central];
            }
        }
        std::size_t j, resultado = 0;
        #pragma omp parallel default(shared) private(j) num_threads(NUMERO_THREADS)
        {
		#pragma omp for schedule(dynamic,1) nowait reduction(+:resultado)
		for (j = 0; j < NL_CONTEX; ++j) {
		    bool localizado = true;
		    std::size_t i;
		    for (i = 1; i <= ContexEsq.size(); ++i) {
			if (tabela_contextual[j][posCentro - i] != ContexEsq[ContexEsq.size() - i]) {
			    localizado = false;
			    break;
			}
		    }
		    if (!localizado) continue;
		    if (etiq_central != 0) {
			if (etiq_central != tabela_contextual[j][posCentro])
			    continue;
		    }
		    for (i = 1; i <= ContexDir.size(); ++i) {
			if (tabela_contextual[j][posCentro + i] != ContexDir[i - 1]) {
			    localizado = false;
			    break;
			}
		    }
		    if (localizado) {
			resultado += ocorrencias[j];
		    }
		}
	}
        return resultado;
    }
    void CarregarTabelaPalavras(void)
    {
        TIPO_GENE indice_etiqueta;
        std::size_t aux_ocorrencia;
        std::fstream fonte_pal;
        char linha[1024*64];
        std::string palavra;
        std::string abv_etiqueta;
        std::vector<std::pair<TIPO_GENE, std::size_t> > lista_pares_etiquetas_ocorrencias;
        fonte_pal.open("tabelas/etiquetas_palavra.txt", std::fstream::in);
        if (fonte_pal.rdstate() & std::fstream::failbit) {
            std::cout << "Não foi encontrado o arquivo tabelas/etiquetas_palavra.txt." << std::endl;
            exit(1);
        }
        while (fonte_pal.getline(linha, 1024*64)) {
            std::istringstream componente(linha);
            componente >> palavra;
            while (componente >> abv_etiqueta) {
                indice_etiqueta = (*TABELA_NUMERICA_ETIQUETAS)[abv_etiqueta];
                if (!(componente >> aux_ocorrencia)) {
                    std::cout << "Inconsistência no arquivo etiquetas_palavra.txt, faltando o nro de ocorrencias na palavra " << palavra << " da etiqueta " << abv_etiqueta << std::endl;
                    exit(1);
                }
                lista_pares_etiquetas_ocorrencias.push_back(std::make_pair(indice_etiqueta, aux_ocorrencia));
            }
            palavras_conhecidas[palavra] = lista_pares_etiquetas_ocorrencias;
            lista_pares_etiquetas_ocorrencias.clear();
        }
        fonte_pal.close();
    }
    void CarregarTabelaDeContexto(void)
    {
        char dados[1024*64];
        std::fstream tt;
        tt.open("tabelas/tabela_referencia.txt", std::fstream::in);
        if (tt.rdstate() & std::fstream::failbit) {
            std::cout << "Não foi encontrado o arquivo tabelas/tabela_referencia.txt." << std::endl;
            exit(1);
        }
        std::size_t n_linha = 0;
        if (tt.getline(dados, 1024*64)) {
            std::istringstream cabecalho(dados);
            cabecalho >> l_CE;
            cabecalho >> l_CD;
            cabecalho >> NL_CONTEX;
        } else {
            std::cout << "Erro no programa: durante a leitura do cabeçalho" << std::endl;
            exit(1);
        }
        // A posição da etiqueta entral coincide numericamente ao valor do tamanho do contexto esquerdo.
        posCentro = l_CE;
        l_TOTAL = l_CE + 1 + l_CD;
        tabela_contextual.reserve(NL_CONTEX);
        ocorrencias.reserve(NL_CONTEX);
        tabela_contextual.clear();
        ocorrencias.clear();
        for (std::size_t i = 0; i < NL_CONTEX; ++i)
            tabela_contextual.push_back(new TIPO_GENE[l_TOTAL]);
        n_linha = 0;
        while ((n_linha < NL_CONTEX) && tt.getline(dados, 1024*64)) {
            std::istringstream n_gramas(dados);
            for (std::size_t col = 0; col < l_TOTAL; ++col) {
                std::string abv_etq;
                if (!(n_gramas >> abv_etq)) {
                    std::cout << "Inconsistência no arquivo treino_x_y.txt. Esperava-se ler " << (l_TOTAL + 1) << " valores na linha " << (n_linha + 1) << std::endl;
                    exit(1);
                }
                tabela_contextual[n_linha][col] = (*TABELA_NUMERICA_ETIQUETAS)[abv_etq];
            }
            std::size_t occ = 0;
            if (!(n_gramas >> occ)) {
                std::cout << "Inconsistência no arquivo treino_x_y.txt. Esperava-se ler " << (l_TOTAL + 1) << " valores na linha " << (n_linha + 1) << std::endl;
                exit(1);
            }
            ocorrencias.push_back(occ);
            ++n_linha;
        }
        tt.close();
        if (n_linha != NL_CONTEX) {
            std::cout << "Erro no programa: declaração do número de contexto é inconsistente" << std::endl;
            exit(1);
        }
    }
};

// A etiqueta da classe gramatical da palavra corresponde numericamente ao gene
class Individuo
{
public:
    std::size_t ComprGenoma;
    double adaptacao; // Valor do fitness
    double rank;
    TIPO_GENE *cromossomo;
private:
    // Vetores para manipulação de contextos deste indivíduo.
    std::vector<TIPO_GENE> ContexEsq;
    std::vector<TIPO_GENE> ContexDir;
public:
    // Contém informações relevantes ao indivíduo
    Individuo(std::size_t n, std::size_t comprContexEsq, std::size_t comprContexDir) : ComprGenoma(n)
    {
        // Reservando espaços mínimos e suficientes para os vetores contextuais.
        ContexEsq.reserve(comprContexEsq);
        ContexDir.reserve(comprContexDir);
        cromossomo = new TIPO_GENE[ComprGenoma];
        // Preenchendo o cromossomo inicial com valores de alelos nulos.
        for (std::size_t i = 0; i < ComprGenoma; ++i)
            cromossomo[i] = 0;
        adaptacao = 0;
        rank = 0;
    }
    // Desfaz a existência do indivíduo
    ~Individuo()
    {
        delete [] cromossomo;
    }
    // Serve para visualizar o cromossomo do indivíduo
    void imprimirCromossomo(std::vector<std::string> &seg, std::ostream *saida = &(std::cout))
    {
        std::size_t locus = 0;
        for (; locus < ComprGenoma; ++locus)
            (*saida) << seg[locus] << "_" << (*QUADRO_DE_ABREV_DAS_ETIQUETAS)[cromossomo[locus]] << " ";
        (*saida) << std::endl;
    }
    // Elabora os vetores de contexto esquerdo e direito a partir do cromossomo deste indivíduo para locus solicitado,
    // e com os tamanhos compEsq e compDir
    void formarVetoresDeContexto(std::size_t locus, std::size_t compEsq, std::size_t compDir)
    {
        ContexEsq.clear();
        ContexDir.clear();
        std::size_t i,j,t;
        if (locus<compEsq) {
            for (i = 0; i < (compEsq - locus); ++i) {
                ContexEsq.push_back(0);
            }
            j = 0;
            for (i = (compEsq - locus); i < compEsq; ++i) {
                ContexEsq.push_back(cromossomo[j++]);
            }
        } else {
            j = (locus - compEsq);
            for (i = 0; i < compEsq; ++i) {
                ContexEsq.push_back(cromossomo[j++]);
            }
        }
        t = ComprGenoma - (locus + 1);
        if (t<compDir) {
            j = 0;
            for (i = 0; i < t; ++i) {
                ContexDir.push_back(cromossomo[locus+1+j]);
                ++j;
            }
            for (i = t; i < compDir; ++i) {
                ContexDir.push_back(0);
            }
        } else {
            j = locus + 1;
            for (i = 0; i < compDir; ++i) {
                ContexDir.push_back(cromossomo[j++]);
            }
        }
        // Encurtar os vetores de contextos quando:
        // 1) os contextos esquerdos iniciam com genes nulos.
        while (ContexEsq.size() && (ContexEsq.front() == 0)) {
            ContexEsq.erase(ContexEsq.begin());
        }
        // 2) os da direita terminam com genes nulos.
        while (ContexDir.size() && (ContexDir.back() == 0)) {
            ContexDir.pop_back();
        }
    }
    // Gera o indivíduo inicial
    // Estratégia:
    //	a) Para cada palavra, localizar a lista de etiquetas viáveis e selecionar
    //	uma desta etiqueta ao acaso, este será o gene correspondente.
    //	b) Caso não exista a palavra conhecida, tentar preencher com etiquetas
    //	em potencial de acordo o contexto formulado.
    //	c) Caso lista_mutacao seja provida (não vazia), aplicar a mutação em cada
    //	alelo de acordo com a lista, caso seja vazia, a todos os genes (para criação inicial).
    void gerarCromossomoInicial(std::vector<std::string> &SegmentoTextual, TabelasTreinadas &Tabela)
    {
        // Estratégia 1)
        // Tentar preencher com etiquetas de palavras conhecidas
        std::size_t locus = 0;
        for (auto &w : SegmentoTextual) {
            TIPO_GENE gene_preliminar = 0;
            gene_preliminar = Tabela.DerivarUmGene(w);
            // Evitar preencher com gene nulo.
            if (gene_preliminar)
                cromossomo[locus] = gene_preliminar;
            ++locus;
        }
        // Estratégia 2)
        // Tentar preencher os alelos nulos pelo contexto das etiquetas laterais.
        for (locus = 0; locus < ComprGenoma; ++locus) {
            if (0 == cromossomo[locus])  {
                TIPO_GENE gene_preliminar = 0;
                std::size_t lce = Tabela.l_CE, lcd = Tabela.l_CD;
                std::size_t alternancia = 0;
                do {
                    formarVetoresDeContexto(locus, lce, lcd);
                    gene_preliminar = Tabela.DerivarUmGenePeloContexto(ContexEsq, ContexDir);
                    // Evitar preencher com gene nulo.
                    if (gene_preliminar) {
                        cromossomo[locus] = gene_preliminar;
                        break;
                    }
                    if ((lce + lcd) == 0) break;
                    if (alternancia % 2) {
                        if (lce) --lce;
                    } else {
                        if (lcd) --lcd;
                    }
                    ++alternancia;
                } while (1);
            }
        }
    }
    // Processar a mutação neste indivíduo.
    // Semelhante ao método de construção da população inicial.
    void mutarIndividuo(std::vector<std::string> &SegmentoTextual, TabelasTreinadas &Tabela, double Pm)
    {
        std::size_t locus = 0;
        for (auto &w : SegmentoTextual) {
            // Obedecer a taxa de mutação.
            if (GNA->Uniform() < Pm) {
                // Estratégia 1)
                // Tentar preencher com etiquetas de palavras conhecidas
                TIPO_GENE gene_preliminar = 0;
                gene_preliminar  = Tabela.DerivarUmGene(w);
                // Evitar preencher com gene nulo e então fazer a substituição.
                if (gene_preliminar) {
                    cromossomo[locus] = gene_preliminar;
                } else {
                    // Estratégia 2)
                    // Tentar preencher com pelo contexto das etiquetas laterais.
                    // Lacunas nulas na posição do alelo, tentar preencher com um novo gene incondicionalmente.
                    std::size_t lce = Tabela.l_CE, lcd = Tabela.l_CD;
                    std::size_t alternancia = 0;
                    do {
                        formarVetoresDeContexto(locus, lce, lcd);
                        gene_preliminar = Tabela.DerivarUmGenePeloContexto(ContexEsq, ContexDir);
                        // Evitar preencher com gene nulo.
                        if (gene_preliminar) {
                            cromossomo[locus] = gene_preliminar;
                            break;
                        }
                        if ((lce + lcd) == 0) break;
                        if (alternancia % 2) {
                            if (lce) --lce;
                        } else {
                            if (lcd) --lcd;
                        }
                        ++alternancia;
                    } while (1);
                }
            }
            ++locus;
        }
    }
    void fixarRank(double R)
    {
        rank = R;
    }
    double obterRank(void)
    {
        return rank;
    }
    void removerFitness(void)
    {
        adaptacao = 0;
        rank = 0;
    }
    // Realiza o cálculo do valor da adaptação deste indivíduo.
    void calcularFitness(TabelasTreinadas &Tabela)
    {
        adaptacao = 0;
        for (std::size_t locus = 0; locus < ComprGenoma; ++locus) {
            std::size_t compEsq = Tabela.l_CE;
            std::size_t compDir = Tabela.l_CD;
            std::size_t alternancia = 0;
	    // Escolhendo de qual direção os contextos não sucedidos vão ser inicialmente removidos.
            std::size_t direcao = GNA->RandInt(2);
            std::size_t occ_ce_t_cd = 0;
            double log_probabilidade = 1;
            do {
                formarVetoresDeContexto(locus, compEsq, compDir);
                compEsq = ContexEsq.size();
                compDir = ContexDir.size();
                log_probabilidade = Tabela.localizarNoCacheAcelerado(ContexEsq, cromossomo[locus], ContexDir);
                if (1 != log_probabilidade) break; // Já existe em cache.
                occ_ce_t_cd = Tabela.recuperarOcorrenciasContextuais(ContexEsq, cromossomo[locus], ContexDir);
                if (occ_ce_t_cd) break;
                if ((compEsq + compDir) == 0) {
                    std::cout <<  "Erro no método obterFitness: contextos de tamanho zero, mas não encontrou ocorrencias do contexto desejado." << std::endl;
                    exit(1);
                };
                if (direcao == (alternancia % 2)) {
                    if (compEsq)
                        --compEsq;
                    else
                        --compDir;
                } else {
                    if (compDir)
                        --compDir;
                    else
                        --compEsq;
                }
                ++alternancia;
            } while (1);
            if (1 == log_probabilidade) { // Não existe em cache.
                std::size_t occ_ce_tlinha_cd = Tabela.recuperarOcorrenciasContextuais(ContexEsq, 0, ContexDir);
                double probabilidade = ((double) occ_ce_t_cd) / ((double) occ_ce_tlinha_cd);
                if (probabilidade > 0) {
                    log_probabilidade = std::log10(probabilidade);
					// Se ainda cabe no cache
					if (Tabela.cache_aceleracao.size() < ENTRADAS_CACHE) {
						Tabela.cache_aceleracao.emplace_back(ContexEsq, cromossomo[locus], ContexDir, log_probabilidade);
					} else {
						// Sortear um local aleatorio para inserir.
						std::size_t local = GNA->RandInt(ENTRADAS_CACHE);
						Tabela.cache_aceleracao[local] = std::make_tuple(ContexEsq, cromossomo[locus], 	ContexDir, log_probabilidade);
					}
                    //Tabela.limitarTamanhoCacheAcelerado();
                } else {
                    std::cout <<  "Erro no método obterFitness: probabilidade de valor zero." << std::endl;
                    exit(1);
                }
            }
            adaptacao += log_probabilidade;
        }
    }

// Devolve o valor da adaptação calculada.
    double obterFitness(void)
    {
        return adaptacao;
    }
// Realiza efetivamente  a recombinação de genes entre dois indivíduos.
// A propabilidade de cruzamento em um locus é a mesma para todo o cromossomo.
    void recombinar(const Individuo *parceiro, Individuo *filho_1, Individuo *filho_2)
    {
        for (std::size_t n = 0; n < ComprGenoma; ++n) {
            if (GNA->RandInt(2)) {
                filho_1->cromossomo[n] = cromossomo[n];
                filho_2->cromossomo[n] = parceiro->cromossomo[n];
            } else {
                filho_1->cromossomo[n] = parceiro->cromossomo[n];
                filho_2->cromossomo[n] = cromossomo[n];
            }
        }
    }
    void invalidarContextos(void)
    {
        ContexEsq.clear();
        ContexDir.clear();
    }
    void copiarPara(Individuo *I)
    {
        I->adaptacao = this->adaptacao;
        I->rank = this->rank;
        I->ComprGenoma = this->ComprGenoma;
        for (std::size_t i = 0; i < this->ComprGenoma; ++i)
            I->cromossomo[i] = this->cromossomo[i];
        I->invalidarContextos();
    }
};

class Populacao
{
    // Lista de indivíduos.
    std::vector<Individuo *> individuo;
public:
    // Retenção do melhor valor de fitness para a atual população.
    double melhorFitness;
    std::size_t indiceMelhorIndividuo;
public:
    Populacao(std::size_t tam_pop, std::size_t comp_cromo, std::size_t comprContexEsq, std::size_t comprContexDir)
    {
        if ((tam_pop % 2) || (tam_pop == 0)) {
            std::cout << "O tamanho da população deve ser par." << std::endl;
            exit(1);
        }
        while (tam_pop--)
            individuo.push_back(new Individuo(comp_cromo, comprContexEsq, comprContexDir));
    }
    ~Populacao()
    {
        for (auto &ap_individ : individuo)
            delete ap_individ;
        MOSTRAR("Liberando população")
    }
    Individuo *obterIndividuo(std::size_t indice)
    {
        return individuo[indice];
    }
    std::size_t obterTamanho(void)
    {
        return individuo.size();
    }
    // Apenas imprime o melhor indivíduo.
    void imprimir(std::vector<std::string> &seg, std::ostream *saida = &(std::cout))
    {
        //for (std::size_t i = 0; i < individuo.size(); ++i) {
        individuo[indiceMelhorIndividuo]->imprimirCromossomo(seg, saida);
        //(*saida)<<" (i=" <<i<<", fit="<<individuo[i]->obterFitness()<<", rank="<<individuo[i]->obterRank()<<")\n";
        // }
    }
    void gerarPopulacaoInicial(std::vector<std::string> &seg, TabelasTreinadas &tabs)
    {
        //~ lista_mutacao.clear();
        for (auto &ap_individ : individuo)
            ap_individ->gerarCromossomoInicial(seg, tabs);
#if DEPURAR
        imprimir(seg);
#endif // DEPURAR
    }
    //The modern version of the Fisher–Yates shuffle by Durstenfeld,
    //http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
    //for i from n − 1 downto 1 do
    //  j ← random integer with 0 ≤ j ≤ i
    //  exchange a[j] and a[i]
    void desordenarCromossomos(void)
    {
        MOSTRAR("Desordenando os cromossomos da população:");
        for (std::size_t i =  individuo.size() - 1; i > 0; --i) {
            std::size_t j = GNA->RandInt(i + 1);
            Individuo *aux = individuo[i];
            individuo[i] = individuo[j];
            individuo[j] = aux;
        }
    }
    // Realiza a ordenação do vetor onde está armazenado o indivíduo.
    void ordenarIndividuosPorFitness(void)
    {
        MOSTRAR("Ordenando os cromossomos da população:");
        // Requer -std=c++11 no compilador
        std::sort(individuo.begin(), individuo.end(), [](Individuo *a, Individuo *b) {
            return a->obterFitness() < b->obterFitness();
        });
    }
    // Realiza o cálculo de fitness em toda população e armazena o melhor fitness para controle.
    // A fazer: Se 1 indivíduo é idêntico ao seguinte na lista apenas copiar o valor o fitness para o mesmo.
    void calcularFitnessPop(TabelasTreinadas &tabs)
    {
        // O menor double representável.
        melhorFitness = std::numeric_limits<double>::lowest();
        std::size_t indice;
        for (auto &ap_individ : individuo) {
            // Solicitação do cálculo de fitness individual.
            ap_individ->calcularFitness(tabs);
            // Realiza a busca do melhor fitness desta geração.
            double candidatoMelhor = ap_individ->obterFitness();
            if (candidatoMelhor > melhorFitness) {
                melhorFitness = candidatoMelhor;
                indiceMelhorIndividuo = indice;
            }
            ++indice;
        }
    }
    double obterFitnessDoIndividuo(std::size_t indice)
    {
        return individuo[indice]->obterFitness();
    }
    // Realiza a recombinação em toda população a uma taxa de Pc.
    // A operação invalida alguns indivíduos da população atual já que pose ser transferida para a nova geração.
    // O tamanho da população deve ser um número par de indivíduos.
    void crossover(double Pc, std::size_t selecionados[], Populacao *Png)
    {
#if DEPURAR
        std::cout << "Aplicando recombinação a uma taxa de Pc=" << Pc << "\n";
#endif
        std::size_t  n_rec = 0;
        std::size_t  N = individuo.size();
        for (std::size_t  m = 0; m < N; m += 2) {
            if (GNA->Uniform() < Pc) {
                individuo[selecionados[m]]->recombinar(individuo[selecionados[m+1]], Png->individuo[m], Png->individuo[m+1]);
                ++n_rec;
            } else {
                individuo[selecionados[m]]->copiarPara(Png->individuo[m]);
                individuo[selecionados[m+1]]->copiarPara(Png->individuo[m+1]);
            }
        }
#if DEPURAR
        std::cout<<"Nesta iteração, o número de recombinações foram: "<<n_rec<<"\n";
#endif
    }
    // Aplica a operação de mutação em toda a população, obedecendo a taxa de mutação Pm.
    void aplicarMutacao(double Pm, std::vector<std::string> &SegmentoTextual, TabelasTreinadas &Tabela)
    {
        for (auto &p : individuo) {
            p->mutarIndividuo(SegmentoTextual, Tabela, Pm);
        }
    }
};

class SGA
{
private:
    // População ativa.
    Populacao *P = NULL;
    // População da geração sucessora.
    Populacao *novaP = NULL;
    // Lista de índices dos indivíduos selecionados
    std::size_t *selecionados = NULL;
    // Segmento de texto a ser etiqueado.
    std::vector<std::string> seg;
    // As tabelas de consulta.
    TabelasTreinadas tabs;
    // Coletor de fitness intermediários.
    double *resultados = NULL;
    // Indicador que a evolução já foi executada uma vez.
    bool evoluido = false;
public:
    SGA()
    {
        // Usando o número de segundos desde 0h:00m de 1/1/1970 como a
        // semente para o gerador de números aleatórios.
        GNA->SetSeed(time(NULL));
    }
    void fazerLimpeza(void)
    {
        MOSTRAR("Liberando a lista de seleção")
        delete P;
        delete novaP;
        delete [] selecionados;
        delete [] resultados;
        P = NULL;
        novaP = NULL;
        selecionados = NULL;
        seg.clear();
        resultados = NULL;
    }
    ~SGA()
    {
        fazerLimpeza();
    }
    void fazerNovoPreparativo(std::vector<std::string> &segmento_texto, std::size_t n_individuos)
    {
        fazerLimpeza();
        evoluido = false;
        // A população inicial de indivíduos.
        P = new Populacao(n_individuos, segmento_texto.size(), tabs.l_CE, tabs.l_CD);
        // A população da geração sucessora, com o mesmo número de indivíduos da população antecessora.
        novaP = new Populacao(n_individuos, segmento_texto.size(), tabs.l_CE, tabs.l_CD);
        // Reserva de espaço de índices a indivíduos selecionados.
        selecionados = new std::size_t[n_individuos];
        // Referência para a sequencia de palavras a serem etiquetadas.
        seg = segmento_texto;
    }
    /* Nesta implementação de seleção por torneio, 2 indivíduos são selecionados com probabilidade uniforme,
    e o indivíduo com melhor fitness é escolhido. Lembrando que é permitido selecionar o mesmo indivíduo
    mais de uma vez, caso ocorra. */
    void selecaoTorneioBinario(void)
    {
        MOSTRAR("Aplicando seleção na população via Torneio, resultando na lista de indivíduos aptos.")
        std::size_t N = P->obterTamanho();
        for (std::size_t i = 0; i < N; ++i) {
            std::size_t idx_1 = GNA->RandInt(N);
            std::size_t idx_2 = GNA->RandInt(N);
            selecionados[i] = P->obterFitnessDoIndividuo(idx_1) > P->obterFitnessDoIndividuo(idx_2) ? idx_1 : idx_2;
#if DEPURAR
            std::cout<<selecionados[i]<<" ";
#endif // DEPURAR
        }
        MOSTRAR("\nFim Torneio")
    }
    /* Implementa a seleção de indivíduos via roleta tradicional SGA. */
    //~ void selecaoRoleta(void) {
    //~ MOSTRAR("Aplicando seleção na população via Roleta, resultando na lista de indivíduos seletos:")
    //~ const int N = P->obterTamanho();
    //~ double somaF = 0;
    //~ for (int i = 0; i < N; ++i)
    //~ somaF += P->obterIndividuo(i)->obterFitness();
    //~ for (int i = 0; i < N; ++i) {
    //~ double r = GNA->Uniform(0, somaF);
    //~ // Inspirado de http://stackoverflow.com/a/8463663
    //~ for (int j = 0; j < N; ++j) {
    //~ r -= P->obterIndividuo(j)->obterFitness();
    //~ if (r < 0) {
    //~ selecionados[i] = j;
    //~ break;
    //~ }
    //~ }
    //~ #if DEPURAR
    //~ std::cout<<selecionados[i]<<" ";
    //~ #endif // DEPURAR
    //~ }
    //~ MOSTRAR("\nFim Sel. Roleta")
    //~ }
    /* Implementa a seleção de indivíduos via roleta tradicional SGA. */
    //~ void selecaoRankingLinear() {
    //~ MOSTRAR("Aplicando seleção na população via Rank, resultando na lista de indivíduos seletos:")
    //~ const int N = pop->obterTamanho();
    //~ double somaR = 0;
    //~ pop->ordenarCromossomosPorFitness();
    //~ for (int i = 0; i < N; ++i) {
    //~ somaR += (i + 1);
    //~ pop->obterIndividuo(i)->fixarRank( i + 1 );
    //~ }
    //~ for (int i = 0; i < N; ++i) {
    //~ double r = GNA->Uniform(0, somaR);
    //~ for (int j = 0; j < N; ++j) {
    //~ r -= pop->obterIndividuo(j)->obterRank();
    //~ if (r < 0) {
    //~ selecionados[i] = j;
    //~ break;
    //~ }
    //~ }
    //~ #if DEPURAR
    //~ std::cout<<selecionados[i]<<" ";
    //~ #endif // DEPURAR
    //~ }
    //~ MOSTRAR("\nFim Sel. por Ranking Linear")
    //~ }
    /* Implementa a seleção de indivíduos via roleta tradicional SGA. */
    //~ void selecaoRankingExponencial(double a = 0.99) {
    //~ MOSTRAR("Aplicando seleção na população via Rank, resultando na lista de indivíduos seletos:")
    //~ const int N = pop->obterTamanho();
    //~ double somaR = 0;
    //~ pop->ordenarCromossomosPorFitness();
    //~ for (int i = 1; i <= N; ++i) {
    //~ double rank_i = pow(a, N - i);
    //~ somaR += rank_i;
    //~ pop->obterIndividuo(i - 1)->fixarRank( rank_i );
    //~ }
    //~ for (int i = 0; i < N; ++i) {
    //~ double r = GNA->Uniform(0, somaR);
    //~ for (int j = 0; j < N; ++j) {
    //~ r -= pop->obterIndividuo(j)->obterRank();
    //~ if (r < 0) {
    //~ selecionados[i] = j;
    //~ break;
    //~ }
    //~ }
    //~ #if DEPURAR
    //~ std::cout<<selecionados[i]<<" ";
    //~ #endif // DEPURAR
    //~ }
    //~ MOSTRAR("\nFim Sel. por Ranking Exponencial")
    //~ }
    void misturarSelecao(void)
    {
        MOSTRAR("Misturando a lista de seleção:")
        //The modern version of the Fisher–Yates shuffle by Durstenfeld,
        //http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
        //for i from n − 1 downto 1 do
        //  j ← random integer with 0 ≤ j ≤ i
        //  exchange a[j] and a[i]
        std::size_t N = P->obterTamanho();
        for (std::size_t i = N - 1; i > 0; --i) {
            std::size_t j = GNA->RandInt(i + 1);
            std::size_t aux = selecionados[j];
            selecionados[j] = selecionados[i];
            selecionados[i] = aux;
        }
#if DEPURAR
        for (std::size_t i = 0; i < N; ++i)
            std::cout<<selecionados[i]<<" ";
#endif // DEPURAR
        MOSTRAR("\nFim mistura")
    }
    void evoluir(std::size_t n_geracoes, double Pc, double Pm)
    {
        //if (resultados != NULL)
        //    delete [] resultados;
        if (evoluido) {
            std::cout << "A população já sofreu evolução completa." << std::endl;
            exit(1);
        }
        if (NULL == P) {
            std::cout << "Não existe uma nova população para ser evoluída." << std::endl;
            exit(1);
        }
        resultados = new double[n_geracoes];
        // Criando os cromossomos iniciais para os indivíduos.
        P->gerarPopulacaoInicial(seg, tabs);
        // Calculando o primeiro fitness dos indivíduos da população.
        P->calcularFitnessPop(tabs);
        std::size_t i = 0;
        // Armazena os valores dos melhores fitness das populações intermediárias.
        resultados[i++] = P->melhorFitness;
        for (; i < n_geracoes;) {
            // Aplicando a pressão seletiva e escolhendo os pais.
            selecaoTorneioBinario();
            //selecaoRoleta();
            //selecaoRankingLinear();
            //selecaoRankingExponencial(0.5);
            // Aleatorizar os índices para os indivíduos selecionados.
            //misturarSelecao();
            // Aplicar a operação de recombinação do AG, gerando uma nova população.
            P->crossover(Pc, selecionados, novaP);
            // Aplicar a operação de mutação do AG na nova população.
            novaP->aplicarMutacao(Pm, seg, tabs);
            // Cálculo do fitness da geração seguinte.
            novaP->calcularFitnessPop(tabs);
            // Armazena os valores dos melhores fitness das populações intermediárias.
            resultados[i] = novaP->melhorFitness;
            // A nova geração como sendo a população sucessora.
            Populacao *substituir = P;
            P = novaP;
            novaP = substituir;
            // Implementa a condição de parada antecipada do AG, caso os dois últimos resultados não mudarem.
            double diff = resultados[i] - resultados[i-1];
            ++i;
            //if (diff<0)
            //    diff = -diff;
            //if (diff < 0.00001) {
            //    std::cout << "Parada antecipada do AG." << std::endl;
            //    break;
            //}
        }
        evoluido = true;
        imprimirResultados(i);
        // Mostrando os cromossomos da última seleção de indivíduos.
        std::fstream saida;
        saida.open("cromo.dat", std::fstream::out | std::fstream::app);
        //saida<<"N,pc,pm,ng = " << P->obterTamanho() << " " << Pc << " " << Pm << " " << n_geracoes << "\n";
        //P->ordenarIndividuosPorFitness();
        std::cout << "Melhor indivíduo:" << std::endl;
        P->imprimir(seg,&saida);
        saida.close();
    }
    void imprimirResultados(std::size_t n_geracoes_criadas)
    {
        //P->ordenarIndividuosPorFitness();
        //P->imprimir(seg);
        for (std::size_t i = 0; i < n_geracoes_criadas; ++i) {
            std::cout << resultados[i];
            if (i + 1 < n_geracoes_criadas)
                std::cout << " ";
            else
                std::cout << std::endl;
        }
    }
};
